package 中等.树;

import util.TreeNode;

/**
 * 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 
 * 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
 * 两个节点之间的路径长度 由它们之间的边数表示。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-univalue-path
 */
public class 最长同值路径_687 {

    public static void main(String[] args) {

    }

    private int count = 0;

    /**
     * 确定某个 node 节点的最长路径
     * 等于它的 左子树中最长相同值路径 + 右子树中最长相同值路径
     *
     * @param root
     * @return
     */
    public int longestUnivaluePath(TreeNode root) {
        findPath(root);
        return count;
    }

    private int findPath(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 左子树最长路径
        int lC = findPath(node.left);
        int rC = findPath(node.right);

        int leftC = 0, rightC = 0;
        // 当前节点是否能和左子树最长路径连接起来
        if (node.left != null && node.val == node.left.val) {
            leftC = lC + 1;
        }
        if (node.right != null && node.val == node.right.val) {
            rightC = rC + 1;
        }
        count = Math.max(count, leftC + rightC);
        return Math.max(leftC, rightC);
    }

}
